#include <stdio.h>
#include <stdlib.h>

#include "dulinklist.h"


/*
 * 初始化
 *
 * 初始化成功则返回OK，否则返回ERROR。
 */
Status InitList(DuLinkList* L)
{
    DuLinkList temp;
    temp = malloc(sizeof(DuLNode));
    if (temp == NULL)
    {
        return OVERFLOW;
    }
    
    *L = temp;

    (*L)->prior = (*L);
    (*L)->next = (*L);

    return OK;
}

/*
 * 销毁(结构)
 *
 * 释放双向循环链表所占内存。
 */
Status DestroyList(DuLinkList* L)
{
    Status ret;
    if (L == NULL || (*L) == NULL)
    {
        return ERROR;
    }
     
    ret = ClearList(*L);
    if (ret != OK)
    {
        return ERROR;
    }
    
    free(*L);

    *L = NULL;

    return OK; 
}


/*
 * 置空(内容)
 *
 * 这里需要释放双向循环链表中非头结点处的空间。
 */
Status ClearList(DuLinkList L)
{
    DuLinkList p,q;

    if (L == NULL)
    {
        return ERROR;
    }

    p = L->next;

    while (p != L)
    {
        q = p->next;
        free(p);
        p = q;
    }

    L->next = L->prior = L;   

    return OK;
}


/*
 * 判空
 *
 * 判断双向循环链表中是否包含有效数据。
 *
 * 返回值：
 * TRUE : 双向循环链表为空
 * FALSE: 双向循环链表不为空
 */
Boolean ListEmpty(DuLinkList L)
{
    if (L == NULL)
    {
        return FALSE;
    }
    
    return L->next == L && L->prior==L ? TRUE :FALSE;    
}


/*
 * 计数
 *
 * 返回双向循环链表包含的有效元素的数量。
 */
int ListLength(DuLinkList L)
{
    DuLinkList temp;
    int count = 0;

    if (L == NULL)
    {
        return ERROR;
    }

    temp = L->next;

    while (temp != L)
    {
        ++count;
        temp = temp->next;
    }

    return count;
}



/*
 * 取值
 *
 * 获取双向循环链表中第i个元素，将其存储到e中。
 * 如果可以找到，返回OK，否则，返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。
 * 通常，i的含义应该指索引，即从0开始计数。
 */
Status GetElem(DuLinkList L, int i, ElemType* e)
{
    DuLinkList temp;
    int j;

    if (L == NULL || L->next==L || L->prior == NULL )
    {
        return ERROR;
    }

    temp = L;

    //获取第i-1个值
    for ( j = 0; j < i && temp->next != L; j++)
    {
        temp = temp->next;
    }

    // j>i 说明参数i的值是非法的，i<0了
    if (temp->next == L || j > i)
    {
        return ERROR;
    }
    
    *e = temp->next->elem; 
        
    return OK;
   
}



/*
 * 查找
 *
 * 返回双向循环链表中首个与e满足Compare关系的元素位序。
 * 如果不存在这样的元素，则返回0。
 *
 *【备注】
 * 元素e是Compare函数第二个形参
 */
int LocateElem(DuLinkList L, ElemType e, Boolean(Compare)(ElemType, ElemType))
{
    DuLinkList temp;
    int count = 0;

    if (L == NULL || L->next==L || L->prior == NULL)
    {
        return -1;
    }

    temp = L->next;

    while (temp != L)
    {
        ++count;
        if (Compare(temp->elem,e))
        {
            break;
        }
        temp = temp->next;
    }

    if (temp == NULL)
    {
        return -1;
    }
    
    return count;
}



/*
 * 前驱
 *
 * 获取元素cur_e的前驱，
 * 如果存在，将其存储到pre_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status PriorElem(DuLinkList L, ElemType cur_e, ElemType* pre_e)
{
    DuLinkList temp;
    
    if (L == NULL || L->next==L || L->prior==L)
    {
       return ERROR; 
    }
    
    temp = L->next;

    while (temp != L)
    {
        if (temp->elem == cur_e)
        {
            break;
        }
        temp = temp->next;
    }

    if (temp == L)
    {
        return ERROR;
    }
    
    *pre_e = temp->prior->elem;
    return OK;
}

/*
 * 后继
 *
 * 获取元素cur_e的后继，
 * 如果存在，将其存储到next_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status NextElem(DuLinkList L, ElemType cur_e, ElemType* next_e)
{
    DuLinkList temp;
    
    if (L == NULL || L->next == NULL || L->prior == NULL)
    {
        return ERROR;
    }
    
    temp = L->next;

    while (temp != L)
    {
        if (temp->next->elem == cur_e)
        {
            break;
        }
    
        temp = temp->next;
    }
    if (temp == L)
    {
        return ERROR;
    }
    
    *next_e = temp->elem;
    return OK;
}


/*
 * 获取循环链表L上第i个元素的引用
 *
 * ▓▓▓▓ 注意 ▓▓▓▓
 * 1.加static的含义是当前函数只在DuLinkList中使用，不会被别的文件引用
 * 2.假设链表长度为len，且需要获取第len+1个元素的引用时，由于这里是循环链表，所以返回的是头结点
 */
static DuLinkList GetElemP(DuLinkList L, int i)
{
    DuLinkList temp;
    int j;
    
    if (L == NULL || i<0)
    {
        return NULL;
    }  

    temp = L;    
    for ( j = -1 ; j < i && temp->next != L; j++)
    {
        temp = temp->next;
    }

    //找到第 i 个元素
    if (j == i)
    {
        return temp;
    }
    
    //i值大于list长度+1
    if ( j+1 <i)
    {
        return NULL;
    }
    
    //j+1 == i:在链表的尾部插入
    return L;    
}


/*
 * ████████ 算法2.18 ████████
 *
 * 插入
 *
 * 向双向循环链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListInsert(DuLinkList L, int i, ElemType e)
{
    DuLinkList newnode,temp;
    newnode = malloc(sizeof(DuLNode));
    if (newnode == NULL)
    {
        return ERROR;
    }
    
    newnode->elem = e;

    temp = GetElemP(L,i);
    if (!temp)
    {
        return ERROR;
    }
    
    newnode->prior = temp->prior;
    newnode->next = temp;

    temp->prior->next = newnode;
    temp->prior = newnode;

    return OK;   
}





/*
 * 遍历
 *
 * 用visit函数访问双向循环链表L
 */
void ListTraverse(DuLinkList L, void(Visit)(ElemType))
{
    DuLinkList temp;

    if (L == NULL || L->next == L || L->prior == L)
    {
        return ;
    }

    temp = L->next;
    while (temp != L)
    {
        Visit(temp->elem);
        temp = temp->next;
    }
    printf("\n"); 
}



/*
 * ████████ 算法2.19 ████████
 *
 * 删除
 *
 * 删除双向循环链表第i个位置上的元素，并将被删除元素存储到e中。
 * 删除成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListDelete(DuLinkList L, int i, ElemType* e)
{
    DuLinkList temp;
    temp = GetElemP(L,i);
    if (temp == NULL || temp == L)
    {
        return ERROR;
    }
    
    temp->next->prior = temp->prior;
    temp->prior->next = temp->next;

    *e = temp->elem;

    free(temp);

    return OK;
}